#include "ActiveVar.h"

#include <algorithm>

void ActiveVar::execute() {
    for (auto &func : this->module->get_functions()) {
        if (func->get_basic_blocks().empty()) {
            continue;
        } else {
            func_ = func;  
            live_in.clear();
            live_out.clear();
            def_var.clear();
            use_var.clear();
            get_def_use_var();
            get_live_in_live_out();   
            for (auto bb : func_->get_basic_blocks()) {
                bb->set_live_in(live_in[bb]);
                bb->set_live_out(live_out[bb]);
            }        
        }
    }
    int i=0;
    for (auto &func : this->module->get_functions()) {
        if (func->get_basic_blocks().empty()) {
            continue;
        } 
        else {
            func_ = func; 
            for(auto bb : func_->get_basic_blocks()){
                printf("\n");
                std::cout << bb->get_name() << " IN ";
                for(auto temp : bb->get_live_in()){
                    std::cout << temp->get_name() << " ";
                }
                printf("\n");
                std::cout << bb->get_name() << " OUT ";
                for(auto temp : bb->get_live_out()){
                    std::cout << temp->get_name() << " ";
                }
                i++;
            }
        }
    }
    
    return ;
}

void ActiveVar::get_def_use_var(){                          //基本块中def和use的计算
    for (auto bb : func_->get_basic_blocks()){              //遍历基本块
        def_var.insert({bb,{}});                            //插入基本块
        use_var.insert({bb,{}});
        for(auto instructions : bb->get_instructions()){    //遍历基本块内部instructions
            if (instructions->is_void()) ;
            else {
                def_var[bb].insert(instructions);               //非空在def_var[bb]中插入instruction     
            }  
            if (instructions->is_phi()){
                for (auto i = 0; i < instructions->get_num_operand(); i+=2){
                    auto op = instructions->get_operand(i);
                    if (def_var[bb].find(op) != def_var[bb].end()) continue;
                    use_var[bb].insert(op);
                }
            }
            else {
                for (auto op: instructions->get_operands()) { //遍历一个表达式的所有运算数
                    if (dynamic_cast<BasicBlock*>(op)) continue;
                    if (dynamic_cast<Function*>(op)) continue;                  
                    if (dynamic_cast<ConstantInt*>(op)) continue;               //如果是基本块、函数、常量，不加入use
                    if (def_var[bb].find(op) != def_var[bb].end()) continue;    //如果前面有def过，不加入use
                    use_var[bb].insert(op);                                     //加入use中
                }  
            }  
        }
    }
}

void ActiveVar::get_live_in_live_out(){
    get_def_use_var();                                      //先计算use和def
    for (auto bb : func_->get_basic_blocks()) {             
        live_in.insert({bb, {}});
        live_out.insert({bb, {}});
    }
    bool if_in_change=true;                                                             //判断是否有in改变
    while(if_in_change){                                                                //如果有in改变了
        if_in_change=false;
        for(auto bb : func_->get_basic_blocks()){                                       //遍历基本块
            std::set<Value *> live_out1 = {};                                           //定义基本块out
            for(auto succbb : bb->get_succ_basic_blocks()){                             //遍历所有后继基本块
                std::set<Value *> phi_in_other_bb;                                      //succbb中phi语句中使用了，但不属于bb的变量
                for(auto instr : succbb->get_instructions()){                           //遍历后继基本块succbb的所有语句
                    if(instr->is_phi()){                                                //对于所有phi语句
                        for(auto i=0; i < instr->get_num_operand(); i=i+2){             //如果引用的不是bb的变量，加入到phi_in_other_bb中
                            if(instr->get_operand(i+1) != bb){
                                phi_in_other_bb.insert(instr->get_operand(i));
                            }
                        }
                    }
                }

                std::set<Value *> phi_still_use = {};                                   //去掉phi_in_other_bb中仍可以参与bb的out计算的变量
                for(auto phi_op : phi_in_other_bb){                                     //检查每个变量
                    std::set<Value *> difference_out_def = {};                          //首先检查是否在out和def的差集中，如果在差集中那么一样可以在bb 的out中         
                    auto live_out_succbb=live_out[succbb];
                    auto def_var_succbb=def_var[succbb];
                    std::set_difference(live_out_succbb.begin(), live_out_succbb.end(), def_var_succbb.begin(), def_var_succbb.end(), std::inserter(difference_out_def, difference_out_def.begin()));
                    if (difference_out_def.find(phi_op) != difference_out_def.end()){
                        phi_still_use.insert(phi_op);                                   //如果在差集当中说明可以加入到out中
                        continue;
                    }
                    
                    for (auto use_list : phi_op->get_use_list()){                       //对于待检查变量遍历他的引用表
                        auto use_val = dynamic_cast<Instruction *>(use_list.val_);      //取它所在的表达式
                        auto use_no = use_list.arg_no_;                                 //它所在的序号
                        if (use_val->get_parent() == succbb){                           //表达式需要是succbb的表达式
                            if (use_val->is_phi()){                                     //如果表达式是phi，根据序号确定它来源
                                auto use_bb = use_val->get_operand(use_no+1);
                                if (use_bb == bb){                                      //来源如果是bb，从phi_in_other_bb中去掉
                                    phi_still_use.insert(phi_op);
                                    break;
                                }
                            }
                            else{                                                       //这个表达式属于succbb且不是phi，说明确实可以加入bb的out
                                phi_still_use.insert(phi_op);
                                break;
                            }
                        }
                    }
                }
                for(auto var : phi_still_use){                                          //删除所有可以加入bb的out中的变量
                    phi_in_other_bb.erase(var);
                }

                auto succ_live_in = live_in[succbb];                                     //将所有succbb的in合并得到bb的out
                std::set<Value *> succ_live_in1;
                std::set_difference(succ_live_in.begin(),succ_live_in.end(), phi_in_other_bb.begin(),phi_in_other_bb.end(), std::inserter(succ_live_in1, succ_live_in1.begin()));
                std::set<Value *> tmp;
                std::set_union(live_out1.begin(), live_out1.end(), succ_live_in1.begin(), succ_live_in1.end(), std::inserter(tmp, tmp.begin()));
                live_out1 = tmp;
            }
            live_out[bb] = live_out1;
            auto live_in1 = live_out1;
            std::set<Value *> in1,in2,in3;                                       //计算bb的in，如果有变化，重复循环
            std::set_difference(live_in1.begin(), live_in1.end(), def_var[bb].begin(), def_var[bb].end(), std::inserter(in1, in1.begin()));
            std::set_union(in1.begin(), in1.end(), use_var[bb].begin(), use_var[bb].end(), std::inserter(in2, in2.begin()));
            if (in2.size() > live_in[bb].size()){
                live_in[bb] = in2;
                if_in_change = true;
            }
        }
    }
    return;
}
